Two-party general secure function evaluation (SFE) allows two parties to evaluate any function on their respective inputs x and y, while maintaining the privacy of both x and y. Efficient SFE algorithms enable a variety of electronic transactions, previously impossible due to mutual mistrust of participants. For example, SFE algorithms have been employed in auctions, contract signing and distributed database mining applications. As computation and communication resources have increased, SFE has become truly practical for common use. A malicious SFE model provides a guarantee of complete privacy of the players' inputs.
Fairplay is an exemplary full-fledged implementation of generic two-party SFE with malicious players. See, for example, D. Malkhi et al., “Fairplay: A Secure Two-Party Computation System,” USENIX (2004). Fairplay demonstrates feasibility and efficiency of SFE of many useful functions, represented as circuits of up to approximately 106 gates.
While such existing generic two-party SFE algorithms have significantly improved the privacy of two party transactions, a number of limitations remain, which, if overcome, could further improve the efficency, utility and/or security of generic two-party SFE algorithms. For example, traditional approaches require the verification of an opened check-set s/2 garbled circuits (GCs) and all commitments for the pairs of inputs wires in the s/2 opened check-set. A need exists for improved generic two-party SFE algorithms that allow a reduced number of commitments to be verified for the pairs of wires in the opened check-set, while sufficiently protecting the privacy of the parties.